package com.zengqingfa.algorithm.cz.chapter02;

import java.util.Arrays;

/**
 * @author zengqingfa
 * @className QuickSort
 * @description
 * @create 2021/8/23 22:34
 */
public class QuickSort {

    public static void main(String[] args) {
        Integer[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void sort(Comparable[] arr) {
        int low = 0;
        int high = arr.length - 1;
        sort(arr, low, high);
    }

    public static void sort(Comparable[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        //对数组arr，从low到high进行切分
        int index = partition(arr, low, high);
        //对左边的数组进行排序
        sort(arr, low, index - 1);
        //对右边的数组进行排序
        sort(arr, index + 1, high);
    }

    /**
     * 对数组arr，从索引low到high之间进行分组，返回分组界限对应的索引
     *
     * @param arr
     * @param low
     * @param high
     * @return
     */
    public static int partition(Comparable[] arr, int low, int high) {
        //以左边第一个元素作为基准值
        Comparable base = arr[low];
        //定义一个左指针,指向左边第一个元素
        int left = low;
        //定义一个右指针，指向最右边元素的下一个元素
        int right = high + 1;
        while (true) {
            //先从右边开始扫描,找到一个比基准值小的元素
            while (less(base, arr[--right])) {
                if (right == low) {
                    //扫描到最左边，无需扫描
                    break;
                }
            }
            //从左边开始扫描，找到一个比基准值大的元素
            while (less(arr[++left], base)) {
                if (left == high) {
                    //扫描到最右边，无需扫描
                    break;
                }
            }
            if (left >= right) {
                //扫描完所有的元素结束循环
                break;
            } else {
                //交换left和right索引处的元素
                swap(arr, left, right);
            }
        }
        //最后交换索引处的元素和基准处的元素
        swap(arr,low,right);
        return right;
    }

    public static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    public static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}